Some switches, such as Ethernet switches, receive data frames at one or more ports. A data frame is an organized format of control or header data and payload data. The header data typically include fields such as the source address of the device transmitting the data frame, the destination address or addresses to which the data frame is being transmitted, length/type data indicating the length of the data frame as well as the data type of the payload data, and a frame check sequence field used as a form of error checking in verifying receipt of the data frame by the destination device. The control data are overhead that are used to ensure that the payload data arrive at the destination device. Control data may be modified by the switch before forwarding to the destination device.
The payload data are the data of interest that are sent to the destination device. Examples of payload data include pixel data for image rendering, audio data, text data and control data (e.g., commands requesting that the destination device transmit information back to the original source device).
In some network implementations, data frames may have different sizes. For example, in a typical Ethernet network, frame size may vary from a minimum of 64 bytes to a maximum of 1,518 bytes.
A switch receives and sequentially forwards data frames to an output port for retransmission to another switch or the destination device. In some switches, a memory is employed to temporarily store a received data frame until the needed port becomes free to output that data frame. These types of switches may be referred to as store-and-forward (SAF) switches.
One design criterion for SAF switches is the width of the memory. Increasing the width of the memory increases the memory access raw bandwidth (i.e., accessing more bytes of data stored in the wider memory for every clock cycle). Memory usage can be inefficient, as only a portion of the memory bandwidth is not used when storing smaller data frames (i.e., a small data frame stored in a wide memory leaves a portion of the memory vacant). Thus, the statistical speed, or efficiency of useful bandwidth, decreases as the memory width increases due to the smaller data frames being stored leaving some part of the memory bus width vacant.
To compensate for this, a memory, such as one that is 256 bytes wide, is divided into independently addressable channels. This allows for smaller data frames to be stored in particular channels, which results in more efficient use of memory and increased throughput. As an example, several smaller data frames can be stored together in memory to reduce the amount of vacant space.
A channel is defined as a portion of the total bus width of a memory. A segment is a logical address in the memory that consists of storage elements from each of the n channels in the memory (e.g., a segment may include four channels). A location is a part of memory that is addressable by both a channel address and a segment address.
One operation performed by a switch is the selection of a channel and segment address to store a received data frame. Typically, this is done randomly, which may result in a problem during the selection of a write address in the memory. More particularly, when write addresses are selected randomly, it is possible that the write address selected will map to a memory location presently occupied by another data frame. This requires the write address selector to randomly select another address and check that address to determine if it contains valid data. Thus, if the memory is substantially full when a new data frame is received, the switch may generate several write addresses that map to full memory locations before generating an address that maps to an empty memory location. This slows down the switch's performance and decreases its bandwidth.
In addition, reading data frames randomly stored in memory also decreases the useful bandwidth of the memory. As an example, suppose a memory has four channels and the switch receives a data frame that is two channels wide. If the switch receives a second data frame that is also two channels wide, it may randomly place the second data frame in another segment, leaving the segment with the first data frame with two vacant channels. Thus, as each segment is clocked to output its data, only half of the available bandwidth will be used to output data in each of the two clock cycles.
Some switches face the further constraint of needing to store data frames contiguously so that data frames are not written across multiple segments. This may cause gaps in the memory that cannot be filled. As large data frames are received, they are written into multiple channels of a single segment. If some of the channels in a particular segment are not used, they will remain unused unless a small data frame is received that can be stored into those empty channels of the segment.
Like reference symbols in the various drawings indicate like elements.